﻿//力扣：137. 只出现一次的数字 II
//https://leetcode.cn/problems/single-number-ii/description/


//方法一：哈希表
//时间复杂度：O(n)
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> mp;         // 创建一个哈希表（map），用于存储每个元素及其出现次数

        // 遍历 nums 数组，将每个元素及其出现次数记录在哈希表中
        for (auto x : nums)
        {
            mp[x]++;                        // 如果元素已经存在，次数加 1；否则初始次数为 1
        }

        // 查找出现次数为 1 的元素
        for (auto x : mp)
        {
            if (x.second == 1)              // 如果找到出现次数为 1 的元素
            {
                return x.first;             // 返回该元素（即该元素为结果）
            }
        }

        return -1;                          // 如果没有找到符合条件的元素，返回 -1（理论上不会到达此处）
    }
};





//方法二：位运算
//时间复杂度：O(n)

//算法原理：
//设要找的数位 ret 。
//由于整个数组中，需要找的元素只出现了「⼀次」，其余的数都出现的「三次」，
//因此我们可以根据所有数的「某⼀个⽐特位」的总和 % 3 的结果，快速定位到 ret 的「⼀个⽐特位上」的值是0 还是 1 。
//这样，我们通过 ret 的每⼀个⽐特位上的值，就可以将 ret 给还原出来。

//核心思路：
//1. 位计数：由于其他数字都出现了三次，除了目标数字（即只出现一次的数字），我们可以逐位累加每一位的 1 的出现次数。
//2. 按位还原：每个二进制位上的 1 的计数对 3 取模，如果结果是 1，说明目标数字在这个位上是 1。
class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        int ret = 0;                                    // 初始化结果变量，用于保存目标数字

        for (int i = 0; i < 32; i++)                    // 逐位处理每一位，总共32位（int类型）
        {
            int sum = 0;                                // 用于保存当前位(i)上的 '1' 的计数
            for (auto x : nums)                         // 遍历数组中的每个数字
            {
                // 判断当前数字 `x` 在第 `i` 位是否为 1
                if (((x >> i) & 1) == 1)
                {
                    sum++;                              // 如果 `x` 的第 `i` 位是 1，计数加 1
                }
            }

            sum %= 3;                                   // 对3取模，去掉所有出现三次的 1
            if (sum == 1)                               // 如果剩下的结果为 1，说明只出现一次的数字在第 `i` 位上是 1
            {
                ret |= 1 << i;                          // 把 `ret` 的第 `i` 位设置为 1
            }
        }

        return ret;                                     // 返回只出现一次的数字
    }
};
//扩展：
//如果其他数字都出现了 n 次，我们就对 n 取模，如果结果是 1，说明目标数字在这个位上是 1。